import java.util.Arrays;
import java.util.Comparator;

public class Solution1048 {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        int[] f=new int[words.length];
        Arrays.fill(f,1);
        int ans=1;
        for (int i=1;i<words.length;i++){
            for (int j=0;j<i;j++){
                if (valid(words[j],words[i])){
                    f[i]=Math.max(f[i],f[j]+1);
                }
            }
            ans=Math.max(ans,f[i]);
        }
        return ans;
    }

    private boolean valid(String a, String b) {
        if (b.length()!=a.length()+1){
            return false;
        }
        int rest=1;
        int j=0;
        for (int i=0;i<a.length();i++){
            if (a.charAt(i)==b.charAt(j)){
                j++;
            }else {
                if (rest==0){
                    return false;
                }
                rest=0;
                j++;
                i--;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1048().longestStrChain(new String[]{"a","b","ba","bca","bda","bdca"}));
    }
}
